package com.aikon.wht.paoshan;

/**
 * @author WANGHAITAO273
 */
public class PaoshanOfMysql {

    // 索引
    // 索引数据结构：哈希表/有序数组/树

    // 哈希表：
    // 数组+链表 数组保存键的哈希结果，值放到链表中
    // 哈希表适用于等值查询，不擅范围查询，常用于nosql
    // 有序数组：
    // 等值查询及范围查询皆可，二分法查找时间复杂度logN，在数组中间插入新值需要移动这个值后面的所有值。
    // 树：
    // B+树是通过二叉查找树，再由平衡二叉树，B树（又名B-树）演化而来的，B+树中的B不是代表二叉（binary），而是代表平衡（balance），因为B+树是从最早的平衡二叉树演化而来，但是B+树不是一个二叉树。

    // 二叉查找树是带有特殊属性的二叉树，需要满足以下属性
    // 1.非叶子节点最多拥有两个子节点
    // 2.非叶子节值大于左边子节点、小于右边子节点（左小右大）
    // 3.没有值相等重复的节点
    // 二叉树的查找时间复杂度为O(logN)到O(N)，介于平衡二叉树及顺序查找树中间。

    // 平衡二叉数在二叉查找树的基础上还需满足
    // 1.树的左右两边的深度相差不会大于1
    // 平衡因子：左子树深度减右子树深度
    // 每个节点的查找次数是其高度.查找速度比顺序查找快.但维护一颗平衡二叉树的代价巨大。需要一次或多次左旋或右旋来得到插入或更新后的平衡性。
    // 设平衡二叉树深度为a，树节点总数为n，二叉树每行最大节点数为2^a，n=1+2+4+...+2^a=2n-n=2^(a+1)-1，则a=log(n+1) - 1，故平衡二叉树查找时间复杂度为logn

    // 不用平衡二叉树而用B树的理由：时间复杂度差不多，二叉树节点间逻辑近而物理远，需要更多的操作磁盘，
    // B树查询充分利用磁盘预读，操作发生在内存

    // B树和B+树的区别：
    // B树：有序数组 + 平衡多叉树  B+树：有序数组链表 + 平衡多叉树
    // B+跟B树不同B+树的非叶子节点不保存键值对应的数据，这样使得B+树每个节点所能保存的键值大大增加，叶子节点之间增加了链表，获取所有节点不再需要中序遍历
    // B+树叶子节点保存了父节点的所有键值和键值对应的数据，每个叶子节点的关键字从小到大链接，所以B+树更适合范围查询
    // B+树的根节点键值数量和其子节点个数相等
    // B+的非叶子节点只进行数据索引，不会存实际的键值对应的数据，所有数据必须要到叶子节点才能获取到，所以每次数据查询的次数都一样

    // 在B树的基础上每个节点存储的关键字数更多，树的层级更少所以查询数据更快，所有关键字指针都存在叶子节点，所以每次查找的次数都相同所以查询速度更稳定。除此之外，B+树的叶子节点是跟后序节点相连接的，这对范围查找是非常有用的。
    // B+树的非叶子节点是主键，主键占用的空间越小，每个节点能放的主键就能更多，这就是为什么我们的主键一般不设置太大的原因。主键占用的空间小，能降低树高，减少IO次数。
    // 树高计算数据量：页大小16KB，每个key大小8B，指针6B，所以每页key约1.1k个，树高=n，则数据总量=(1.1k)^n

    // 聚集索引：叶子节点是数据页。
    // 非聚集索引：叶子节点是指向数据的指针。

    // 覆盖索引
    // 最左匹配原则
    // 索引下推
    public static void main(String[] args) {

    }
}
